class Solution:
    def __init__(self):
        self.best = dict()
        self.mult = list()
        self.arr = list()

    def dp(self, first: int, last: int, count: int):
        if count >= len(self.mult):
            return 0

        if (first, last) in self.best:
            return self.best[(first, last)]
        ''''''
        self.best[(first, last)] = max(
            self.arr[first] * self.mult[count] + self.dp(first + 1, last, count + 1),
            self.arr[last] * self.mult[count] + self.dp(first, last - 1, count + 1)
        )
        return self.best[(first, last)]

    def maximumScore(self, nums: list[int], multipliers: list[int]) -> int:
        self.arr = nums
        self.mult = multipliers
        ''''''
        return self.dp(0, len(self.arr) - 1, 0)
